// 712. 两个字符串的最小ASCII删除和


/*
动态规划：
1、题目简化：求使s1和s2相同的最小ASCII删除和
2、定义dp数组：dp[i][j] 表示使 s1前i个字符 和 s2前j个字符 相同的最小ASCII删除和
3、初始化：
  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化
  2）dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); 表示使 s1前i个字符 和 空字符串 相同的最小ASCII删除和，逐个累加
    dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1); 表示使 空字符串 和 s2前j个字符 相同的最小ASCII删除和，逐个累加
4、状态转移方程：
  1）如果s1[i] == s[j]，即两个字符串最后一个字符相同，那么不用删除，结果为 s1前i-1个字符 和 s2前j-1个字符 相同的最小ASCII删除和，即 dp[i][j] = dp[i - 1][j - 1];
  1）如果s1[i] != s[j]，即两个字符串最后一个字符不相同，那么需要删除，使用之前状态的最小ASCII删除和 加上 当前被删除字符的ASCII值，有两种情况是状态已知且字符最多的
    ① 删除s1[i]，即 s1前i-1个字符 和 s2前j个字符 相同的最小ASCII删除和 加上 当前被删除字符的ASCII值，即 dp[i - 1][j] + s1.charAt(i - 1)
    ① 删除s2[j]，即 s1前i个字符 和 s2前j-1个字符 相同的最小ASCII删除和 加上 当前被删除字符的ASCII值，即 dp[i][j - 1] + s2.charAt(j - 1)
    比较这两种情况是因为删除的字符可能是相同的字符，会增加额外的删除操作，两者取最少就得到当前结果，即 dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
5、遍历dp数组填表
  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最小ASCII删除和
  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历字符串s1，内层遍历字符串s2。
    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
    从两个字符串角度看，两个指针分别指向两个字符串，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
6、返回结果：最后一个状态就是结果

s1 = "delete", s2 = "leet"
   ''    l    e    e    t
''  0   108  209  310  426
d  100  208  309  410  526
e  201  309  208  309  425
l  309  201  302  403  519
e  410  302  201  302  418
t  526  418  317  418  302
e  627  519  418  317  403

s1: d  e  l  e  t  e
             ↑
             i
s2: l  e  e  t
          ↑
          j
 */
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
                }
            }
        }
        return dp[n][m];
    }
}